/**
 * @author ChaP
 * @date 2019/05/22
 * @describe:
 */
package CodingTest.AC20190522;


/**leetcode - 450
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

 一般来说，删除节点可分为两个步骤：

 首先找到需要删除的节点；
 如果找到了，删除它。
 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

 示例:

 root = [5,3,6,2,4,null,7]
 key = 3

 5
 / \
 3   6
 / \   \
 2   4   7

 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

 5
 / \
 4   6
 /     \
 2       7

 另一个正确答案是 [5,2,6,null,4,null,7]。

 5
 / \
 2   6
 \   \
 4   7
 */
public class deleteNode {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){val = x;}
    }
    //方法一：
    public TreeNode deleteNode(TreeNode root,int key){
        if(root == null) return null;
        if(key < root.val){
            //待删除节点在左子树
            root.left = deleteNode(root.left,key);
            return root;
        }else if(key > root.val){
            //待删除节点在右子树
            root.right = deleteNode(root.right,key);
            return root;
        }else{
            //key == root.val,root 为待删除节点
            if(root.left == null){
                //返回右子树作为新的根
                return root.right;
            }else if(root.right == null){
                //返回左子树作为新的根
                return root.left;
            }else{
                //左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
                TreeNode successor = min(root.right);
                successor.right = deleteMin(root.right);
                successor.left = root.left;
                return successor;
            }
        }
    }
    //寻找右子树的最左节点
    private TreeNode min(TreeNode node){
        if(node.left == null)return node;
        return min(node.left);
    }

    private TreeNode deleteMin(TreeNode node){
        if(node.left == null)
            return node.right;
        node.left =deleteMin(node.left);
        return node;
    }

//    方法二：
    public TreeNode deleteNode1(TreeNode root,int key){
        if(!containNode(root,key)){
            return null;
        }
        if(root.val == key){
            if(root.left == null){
                //如果root节点的左节点为null，直接返回root节点的右节点
                return root.right;
            }else if(root.right == null){
                //如果root节点的右节点为null，我们直接返回root节点的左节点
                return root.left;
            }
            //如果root节点的左右节点均不为null
            //1.调用findMin()函数，寻找到以root.right的右节点为根节点的二分搜索树中最小的节点，记为successor
            TreeNode successor = findMin(root.right);
            //2.调用delMin()函数，删除以root的右节点为根节点的二分搜索树中的最小的节点，并令其结果作为successor的右节点
            successor.right = delMin(root.right);
            //3.令sucessor的左节点为root的左节点，返回successor节点
            successor.left = root.left;
            return successor;
        }else if(root.val < key){
            //如果root的值比key值小，说明所寻找的节点在root节点的右子树中，递归调用删除节点的函数在以root的右节点为根节点的二分
            //搜索树中删除值为key的节点，并令其返回结果为root的右孩子，返回root节点
            root.right = deleteNode(root.right,key);
            return root;
        }else {
            root.left = deleteNode(root.left,key);
            return root;
        }
    }

    //用来判断在以treeNode为根节点的二分搜索树中是否有值为key的节点。该函数是递归实现的
    public boolean containNode(TreeNode treeNode,int key){
        if(treeNode == null){
            return false;
        }
        if(treeNode.val == key){
            return true;
        }else if(treeNode.val >key){
            return containNode(treeNode.left,key);
        }else{
            return containNode(treeNode.right,key);
        }
    }

    //寻找以treeNode为根的最小值节点
    public TreeNode findMin(TreeNode treeNode){
        TreeNode cur = treeNode;
        while(cur!=null){
            if(cur.left == null){
                return cur;
            }
            cur = cur.left;
        }
        return cur;
    }

    //用来删除在以treeNode为根节点的二分搜索树中值最小的节点，并返回删除最小节点后新的二分搜索树的根节点，递归实现（难点）
    private TreeNode delMin(TreeNode treeNode){
        //终止条件：当前节点没有左子树，那么就是最小节点
        if(treeNode.left == null){
            return treeNode.right;
        }
        treeNode.left = delMin(treeNode.left);
        return treeNode;
    }

}
